import java.util.ArrayList;
import java.util.List;

public class Solution68 {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            //j个单词每个单词接一个空格的长度为len
            int j = 1;
            int len = words[i].length();
            int blank;     //空格数量
            StringBuilder s = new StringBuilder();
            while (len <= maxWidth && i + j < words.length) {
                len += words[i + j].length() + 1;
                j++;
            }
            if (len > maxWidth) {
                j--;
                len = len - words[i + j].length() - 1;
            }
            if (i + j == words.length) {
                s.append(words[i]);
                for (i++; i < words.length; i++) {
                    s.append(" ").append(words[i]);
                }
                s.append(" ".repeat(maxWidth - len));
                res.add(s.toString());
                break;
            }
            blank = maxWidth - len + j - 1;
            int k = j - 1;      //要补空格的位置
            //如果j==1，不执行循环
            for (int count = i + j - 1; i < count; i++) {
                int addBlank = blank / k + (blank % k > 0 ? 1 : 0); //words[i]后面要添加的空格
                s.append(words[i]);
                s.append(" ".repeat(addBlank));
                k--;
                blank -= addBlank;
            }
            s.append(words[i]);
            s.append(" ".repeat(blank));
            res.add(s.toString());
        }

        return res;
    }
}
